1. Field of the Invention
The invention relates generally to the field of computer algorithms and more particularly to a system and method for determining the commutativity of computational operations.
2. Description of the Related Art
Pending computational operations such as updating entries in a database are conventionally stored in an ordered list. For each pending operation on the list, upon execution of the operation, an affected row in the database is locked until a commit or roll back. The affected row is locked in order that other pending operations do not intercede and produce inconsistent results. For example, if the list includes two updates to a cell in the database row, the affected row is locked so that a first update operation executes and commits before a second update operation executes and commits. In this manner, the integrity of the database is maintained.
The execution of such computational operations using locks is expensive. For example, if two cashiers in a store have to post updates to the same account, the cashier who posts his update first proceeds while the cashier who posts his update second has to wait while the first cashier's update is executed. While in this example the productivity of the second cashier may not necessarily be adversely affected by waiting, in a situation where hundreds and possibly thousands of cashiers are posting updates to the same account, such waiting adversely affects the productivity of the cashiers.
With the integration of computational operations enabled by the increase in computational speeds and the decrease in the cost of storage, conventional locking techniques have forced many operations to be done as batched operations. Thus, all updates to a particular account for example, are executed after the close of business so as to maintain the productivity of those making updates to the particular account.
While such batched operations are effective in maintaining account information, their performance does not allow for efficiencies provided by realtime computation. For example, the ordering of inventory in an inventory control system dependent upon batched operations must be performed after the execution of the batched operations rather than in realtime when the inventory is needed.
Using the locking technique of the prior art further requires that the lists of pending operations be processed by server machines generally located in geographically distinct locations from a central location where the database is maintained. Thus an enterprise having operations in a plurality of locations must maintain a server machine at each location at great cost to the enterprise.
Thus, there is a need in the art for a system and method of performing computation operations which provides for realtime computation. Such a system and method preferably reduces the number of server machines required to maintain information in a database.